package OptimalAlgorithm.Hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//https://leetcode.cn/problems/group-anagrams/description/
public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
/*(超过内存限制:由于固定了数组长度)
        HashMap<String,String[]> hash = new HashMap<>();//<字母顺序排序结果（分组结果），每组存储的异位词>
        for (int i = 0; i < strs.length; i++) {
            String s = sort(strs[i]);//将字符串排序，从而判断是否为字母异位词，进行分类
            if(!hash.containsKey(s)){
                String[] arr = new String[strs.length];
                arr[0] = strs[i];
                hash.put(s,arr);
            }else {
                hash.get(s)[i] = strs[i];
            }
        }
        List<List<String>> lists = new ArrayList<>();
        for (Map.Entry<String,String[]> stringEntry: hash.entrySet()) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < strs.length; i++) {
                if(stringEntry.getValue()[i] != null){
                    list.add(stringEntry.getValue()[i]);
                }
            }
            lists.add(list);
        }
        return lists;*/
        HashMap<String,List<String>> hash = new HashMap<>();
        for (String str : strs) {
            String s = sort(str);//将字符串排序，从而判断是否为字母异位词，进行分类
            if (!hash.containsKey(s)) {
                hash.put(s, new ArrayList<>());
            }
            hash.get(s).add(str);
        }
        return new ArrayList<>(hash.values());
    }
    private String sort(String str) {
        int[] hash = new int[26];
        for (int i = 0; i < str.length(); i++) {
            int x = str.charAt(i) - 97;
            hash[x]++;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0){
                stringBuilder.append((char)(i+97));
                hash[i]--;
            }
        }
        return stringBuilder.toString();
    }
}
